(1) Field of the Invention
The present invention relates to an encryption technique for maintaining the security of information, and in particular relates to a multiplication apparatus that performs the necessary calculation for encryption and digital signature techniques which use an elliptic curve
(2) Prior Art
Secret communication techniques allow communication to be performed without the content being revealed to third parties. Digital signature techniques, meanwhile, enable a receiver to verify the validity of the communicated content by confirming that the information is from the stated sender. Such signature techniques use an encryption technique called public key encryption.
Public key encryption provides a convenient method for managing the separate encryption keys of many users, and so has become a fundamental technique for performing communication with a large number of users. In brief, public key techniques use different keys for encryption and decryption, with the decryption key being kept secret and the encryption key being made public. Here, one of the founding principles for the security of public key encryption is the so-called "discrete logarithmic problem". Representative examples of the discrete logarithmic problem are problems defined over finite fields and problems based on elliptic curves. Such problems are described in detail in Neal Koblitz, A Course in Number Theory and Cryptography (Spinger-Verlag, 1987). A discrete logarithmic problem based on an elliptic curve is explained below.
The elliptic curve logarithmic problem is as follows. (E(GF(p)) is the elliptic curve E defined in the finite field GF(p), with the element G, given by dividing the order of E by a large prime number, being set as a base point. This being so, the problem is to find an integer x that satisfies the relationship EQU Y=xG
where the element Y is also given by the elliptic curve E and such value x actually exists.
The reason a discrete logarithmic problem assists in the security of public key encryption is that the above calculation is extremely difficult for a large finite field GF(p), with such calculation corresponding to the calculation of the inverse, or "hard direction", of a one-way function.
The following is a description of the Elsamal signature technique which uses a discrete logarithmic problem based on an elliptic curve.
FIG. 13 shows a conventional configuration for the ElGamal signature algorithm based on an elliptic curve. This procedure is described in detail below.